package com.yuufa.test.matrix;

public class NMatrixProduct {

    public static void main(String[] args) {

        int n = 6;
        int[][] m = new int[n + 1][n + 1];
        int[] d = {3, 2, 6, 7, 2, 2, 8}; // Ai's d[i-1]xd[i]

        // initial
        for (int i = 1; i <= n; i++) {
            m[i][i] = 0;
        }

        for (int diagonal = 1; diagonal < n; diagonal++) {
            for (int i = 1; i <= n-diagonal; i++) {
                int j = i + diagonal;
                
                m[i][j] = Integer.MAX_VALUE;
                for(int k=i;k<j;k++) {
                    int tmp = m[i][k] + m[k+1][j] + d[i-1]*d[k]*d[j];
                    
                    if(m[i][j] > tmp) {
                        m[i][j] = tmp;
                    }
                }
            }
        }
        
        for(int i=1;i<=n;i++) {
            for(int j=1;j<=n;j++) {
                System.out.printf("%4d", m[i][j]);
            }
            System.out.println();
        }
    }
}
